/*
 * @Author: your name
 * @Date: 2020-10-19 09:18:15
 * @LastEditTime: 2020-10-19 10:25:39
 * @LastEditors: your name
 * @Description: In User Settings Edit
 * @FilePath: \javaCode\labuladong\TreeAl.java
 */
package labuladong;

import java.util.Map;

public class TreeAl {
    // 求二叉树最大路径和 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root){
        maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode root){
        if(root==null) return 0;
        int left = Math.max(0, maxGain(root.left));
        int right = Math.max(0, maxGain(root.right));
        maxSum = Math.max(maxSum, left+right+root.val);
        // 返回某个节点能贡献的最大值
        return Math.max(left, right)+root.val;
    }

    /**
     * @description: 根据前序遍历和中序遍历的结果还原一颗二叉树
     * @param: inmap:中序遍历节点和位置的对应关系 
     * @return: 生成树的根据点
     */
    
    TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap ){
        if(preStart > preEnd || inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot-inStart;
        // 注意下标
        root.left = buildTree(preorder, preStart+1, preStart+numsLeft, inorder, inStart, inRoot-1, inMap);
        root.right = buildTree(preorder, preStart+numsLeft+1,preEnd, inorder, inRoot+1, inEnd, inMap);
        return root; 
    }
    
}
